//Best visualisation of AVL trees: 
//http://webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20applet.htm
#pragma once

#ifndef _T2AVLLIST_H_
#define _T2AVLLIST_H_

#include "Utils/T2List.h"

template<class T,class D,bool inverted>class T2AVLnode;

template<class T,class D,bool inverted>class T3AVLListDirected;

template<class T,class D>class T2AVLList; //AVLList with ascending sort
template<class T,class D>class T2AVLListInverted; //AVLList with descending sort

template<class T,class D,bool inverted>class T3AVLListDirected: public T2List<T,D>
{
	friend class T2AVLList<T,D>;
	friend class T2AVLListInverted<T,D>;
	private:
		T2AVLnode<T,D,inverted>* root;
		unsigned int nodeCount;

		T2AVLnode<T,D,inverted>* nodeAt(unsigned int index)
		{
			T2AVLnode<T,D,inverted>* temp = NULL;
			if(index<=nodeCount/2) // start from the first element
			{
				//get the first element (index=0)
				temp = root->getFirst();
				//if the index is > 0: get the next element index times
				for(unsigned int currIndex=0;currIndex<index;currIndex++)
					temp = temp->getNext();
			}
			else //start from the last element
			{
				//get the last element
				temp = root->getLast();
				//if the index is > 0: get the next element index times
				for(unsigned int currIndex=0;currIndex<(nodeCount-index-1);currIndex++)
					temp = temp->getPrev();
			}
			return temp;
		}

		char appendNode(T2AVLnode<T,D,inverted>* newNode)
		/*
		Append a node to the list
		Return values:
		0 - success
		1 - a node with the same key already exists
		*/
		{
			char retVal=1;

			if (root==NULL)
			{
				root=newNode;
				nodeCount++;
				return 0;
			}

			retVal=root->appendNode(newNode);
			root=root->getRoot();

			if (retVal != 0)
			{
				delete newNode;
				return 1;
			}

			nodeCount++;
			return 0;
		}

		public:
		
		T3AVLListDirected()
		/*
		Create a new empty list
		*/
		{
			root=NULL;
			nodeCount=0;
		}

		~T3AVLListDirected()
		/*
		Destroy the list
		*/
		{
			clear();
		}

		char pushFront(T newKey,D newData)
		/*
		Append a new entry to the list
		pushFront and pushBack are equal for an avl list
		Return values:
		0 - success
		1 - a node with the same key already exists
		*/
		{
			return appendNode(new T2AVLnode<T,D,inverted>(newKey,newData));
		}

		char pushBack(T newKey,D newData)
		/*
		Append a new entry to the list
		pushFront and pushBack are equal for an avl list
		Return values:
		0 - success
		1 - a node with the same key already exists
		*/
		{
			return appendNode(new T2AVLnode<T,D,inverted>(newKey,newData));
		}

		D find(T seaKey)
		/*
		Find the data belonging to a key
		*/
		{
			if (root==NULL)
				return NULL;

			T2AVLnode<T,D,inverted>* retVal = root->findNode(seaKey); 
			
			if (retVal!=NULL)
				return retVal->getData();

			return NULL;
		}

		unsigned int getSize()
		/*
		Return the size of the list
		*/
		{
			return nodeCount;
		}

		void clear()
		/*
		Remove all entries from the list, do not do this if the list contains pointers, unless you point to them somewhere else
		*/
		{
			while(root!=NULL)
				removeAt(0);
		}

		T getKeyAt(unsigned int index)//Returns the key for the element at position <index>
		{
			if ((root==NULL) || (index>=nodeCount))
				return NULL;

			T2AVLnode<T,D,inverted>* temp = nodeAt(index);
			return temp->getKey();
		}

		D at(unsigned int index)
		/*
		Return the data stored in position <index> in the list
		*/
		{
			//if the tree is empty or the index is bigger or equal to the number of nodes
			//return NULL
			if ((root==NULL) || (index>=nodeCount))
				return NULL;

			T2AVLnode<T,D,inverted>* temp = nodeAt(index);

			return temp->getData();
		}

		D getFirst()
		/*
		Return the first elements data
		*/
		{
			return at(0);
		}

		D getLast()
		/*
		Return the last elements data
		*/
		{
			return at(nodeCount-1);
		}

		void sort()
		/*
		Sorts the entries in the list by key (ascending).
		Not needed with avl lists, those are always sorted ascending!
		*/
		{
			//AVL List is always sorted ascending!
		}

		void inversesort()
		/*
		Sorts the entries in the list by key (descending).
		Does not work with avl lists, those are always sorted ascending!
		Either use T2AVLListInverted as the backend or search from the back.
		*/
		{
			//AVL List is always sorted ascending!
		}

		
		char removeByKey(T delKey)
		/*
		Remove the entry with key delKey
		Return values:
		0 - success
		1 - no node found with key <delKey>
		2 - tree has no root
		*/
		{
			if (root==NULL)
				return 2;

			T2AVLnode<T,D,inverted>* deleteNode=root->removeNode(delKey);

			if (deleteNode==NULL)
				return 1;

			root=deleteNode->getParent();

			if (root!=NULL)
				root=root->getRoot();

			nodeCount--;

			delete deleteNode;

			return 0;
		}

		char removeAt(unsigned int index)
		/*
		Remove the entry at position <index>
		Return values:
		0 - success
		1 - no node found with key <delKey>
		*/
		{
			T2AVLnode<T,D,inverted>* temp = nodeAt(index);
			if (temp!=NULL)
				return removeByKey(temp->getKey());
			return 0;
		}

		char changeKey(T oldKey, T newKey) 
		/*
		Changes the key for the data associated with <oldKey> to <newKey>
		Return values:
		0 - success
		1 - node found with key <newKey>
		2 - no node found with key <oldKey>
		3 - list has no root
		*/
		{
			if (root == NULL)
				return 3;

			T2AVLnode<T,D,inverted>* retVal;
			
			retVal = root->findNode(newKey); 

			if (retVal!=NULL)
				return 1;

			retVal = root->findNode(oldKey); 
			
			if (retVal==NULL)
				return 2;

			D data = retVal->getData();
			retVal = NULL;

			removeByKey(oldKey);
			
			pushBack(newKey,data);
			return 0;
		}
};

template<class T,class D>class T2AVLList: public T3AVLListDirected<T,D,false>
{
public:
	T2AVLList()
	{
	}

	~T2AVLList()
	{
	}
};

template<class T,class D>class T2AVLListInverted: public T3AVLListDirected<T,D,true>
{
public:
	T2AVLListInverted()
	{
	}

	~T2AVLListInverted()
	{
	}
};

template<class T,class D,bool inverted>class T2AVLnode
{
private:
	T2AVLnode<T,D,inverted> *left;
	T2AVLnode<T,D,inverted> *right;
	T2AVLnode<T,D,inverted> *parent;
	T key;
	D data;
	unsigned char height;
public:

	/*
	Constructors
	*/

	T2AVLnode()
	{
		left=NULL;
		right=NULL;
		parent=NULL;
		height=1;
	}

	T2AVLnode(T newKey,D newData)
	{
		left=NULL;
		right=NULL;
		parent=NULL;
		key=newKey;
		data=newData;
		height=1;
	}

	/*
	get-functiosn for data + key
	*/

	T getKey()
	{
		if (this==NULL)
			return NULL;
		return key;
	}

	D getData()
	{
		return data;
	}

	/*
	get & set functions for height & balance
	*/
private:
	signed char getLeftHeight()
	{
		if (left==NULL)
			return 0;
		return left->getHeight();
	}

	signed char getRightHeight()
	{
		if (right==NULL)
			return 0;
		return right->getHeight();
	}

	signed char getBalance()
	{
		return getRightHeight()-getLeftHeight();
	}

public:
	unsigned char getHeight()
	{
		return height;
	}

	void recalculateHeight()
	{
		height=1+max(getLeftHeight(),getRightHeight());
	}

	/*
	get & set functions for the nodes parent, left and right
	*/
public:
	T2AVLnode<T,D,inverted>* getParent()
	{
		return parent;
	}

private:
	void setParent(T2AVLnode<T,D,inverted>* newParent)
	{
		parent=newParent;
	}

	T2AVLnode<T,D,inverted>* getLeft()
	{
		return left;
	}

	void setLeft(T2AVLnode<T,D,inverted>* newLeft)
	{
		left=newLeft;
	}

	T2AVLnode<T,D,inverted>* getRight()
	{
		return right;
	}

	void setRight(T2AVLnode<T,D,inverted>* newRight)
	{
		right=newRight;
	}

	/*
	function to find a node in the tree.
	*/
public:
	T2AVLnode<T,D,inverted>* findNode(T seaKey)
	{
		if (seaKey == key)
			return this;
		else if ( inverted != (seaKey < key) )
		{
			if (left==NULL)
			{
				return NULL;
			}
			else
				return left->findNode(seaKey);
		}
		else //newKey>key
		{
			if (right==NULL)
			{
				return NULL;
			}
			else
				return right->findNode(seaKey);
		}
	}

	T2AVLnode<T,D,inverted>* getRoot()
	/*
	function that returns the root, determined from the node it is called at
	may be needed after add/remove of the root node
	*/
	{
		if (parent==NULL)
			return this;
		else
			return parent->getRoot();
	}

	private:
	/*
	function to rotate nodes (needed after add/delete) to keep the tree balanced
	*/
	void singleRot(bool leftRot)
	{
		T2AVLnode<T,D,inverted>* temp;
		if (leftRot)
		{
			if ((parent!=NULL) && (right != NULL))
			{
				if (parent->getRight()==this)
					parent->setRight(right);
				else
					parent->setLeft(right);
			}
			if (right!=NULL)
			{
				temp=right->left;
				right->setParent(this->parent);
				right->setLeft(this);
				setParent(right);
				setRight(temp);
				if (right!=NULL)
					right->setParent(this);
			}
		}
		else
		{
			if ((parent!=NULL) && (left!=NULL))
			{
				if (parent->getRight()==this)
					parent->setRight(left);
				else
					parent->setLeft(left);
			}
			if (left!=NULL)
			{
				temp=left->right;
				left->setParent(this->parent);
				left->setRight(this);
				setParent(left);
				setLeft(temp);
				if (left!=NULL)
					left->setParent(this);
			}
		}
		recalculateHeight();

		if (parent!=NULL)
			parent->recalculateHeight();
	}

	void fixHeights()
	/*
	function to fix the height of a node
	recalculates the nodes height and rotates nodes if necessary
	*/
	{
		recalculateHeight();

		if (getBalance()>1)
		{
			if (right->getBalance()==-1)
			{
				right->singleRot(false);
				singleRot(true);
			}
			else
				singleRot(true);
		}
		if (getBalance()<-1)
		{

			if (left->getBalance()==1)
			{
				left->singleRot(true);
				singleRot(false);
			}
			else
				singleRot(false);
		}
	}

	public:
	/*
	function to append a node to the tree and rotate nodes if necessary
	Return values:
	0 - success
	1 - a node with the same key already exists
	*/
	int appendNode(T2AVLnode<T,D,inverted>* newNode)
	{
		if (newNode->getKey() == key)
			return 1; //Key already found in list

		int retVal;

		if ( inverted != ( newNode->getKey() < key ) )
		{
			if (left==NULL)
			{
				left=newNode;
				left->setParent(this);
				if (right==NULL)
					height++;
				retVal=0;
			}
			else
				retVal=left->appendNode(newNode);
		}
		else //newKey>key
		{
			if (right==NULL)
			{
				right=newNode;
				right->setParent(this);
				if (left==NULL)
					height++;
				retVal=0;
			}
			else
				retVal=right->appendNode(newNode);
		}
		fixHeights();
		return retVal;
	}

	/*
	function to delete a node from the tree and rotate nodes if necessary
	returns a pointer to the node that was removed or NULL if no node was removed
	if a node was removed the parent of the returned node can be the used to find the next tree-root
	*/

	public:
	T2AVLnode<T,D,inverted>* removeNode(T delKey)
	{
		if (!(delKey == key))
		{
			T2AVLnode<T,D,inverted>* retVal;
			if ( inverted != ( delKey < key ) )
			{
				if (left==NULL)
					return NULL;
				else
					retVal=left->removeNode(delKey);
			}
			else //delKey>key
			{
				if (right==NULL)
					return NULL;
				else
					retVal=right->removeNode(delKey);
			}

			//if we deleted a node, we need to fix the tree on the way back to the root
			if (retVal!=NULL)
				fixHeights();

			return retVal;
		}

		T2AVLnode<T,D,inverted>* newParent = NULL;
		T2AVLnode<T,D,inverted>* replacementNode = NULL;

		//the current node is the node we want to remove
		//determine how the remove is done
		if (getLeftHeight() >= getRightHeight())
		{
			//check if both subtrees are empty
			if (left==NULL) //equals right == null
			{
				//if this node is not the root:
				//remove this node from the parent
				if (parent!=NULL)
				{
					if (parent->getLeft()==this)
						parent->setLeft(NULL);
					else
						parent->setRight(NULL);
				}
				newParent = parent;
			}
			else //the left subtree is bigger than the right subtree and not empty
			{
				//search the maximal key in the left subtree
				replacementNode = left;
				while (replacementNode->getRight()!=NULL)
					replacementNode = replacementNode->getRight();

				//replace the replacementNode with its subtree
				if (replacementNode->getLeft()!=NULL)
					replacementNode->getLeft()->setParent(replacementNode->getParent());
				
				if (replacementNode->getParent()!=this)
					replacementNode->getParent()->setRight(replacementNode->getLeft());
				else
					this->setLeft(replacementNode->getLeft());
				replacementNode->setLeft(NULL);
			}
		}
		else
		{
			//the right subtree is bigger than the left subtree and not empty
			//search the minimal key in the right subtree
			replacementNode = right;
			while (replacementNode->getLeft()!=NULL)
				replacementNode = replacementNode->getLeft();

			//replace the replacementNode with its subtree
			if (replacementNode->getRight()!=NULL)
				replacementNode->getRight()->setParent(replacementNode->getParent());
			
			if (replacementNode->getParent()!=this)
				replacementNode->getParent()->setLeft(replacementNode->getRight());
			else
				this->setRight(replacementNode->getRight());

			replacementNode->setRight(NULL);
		}

		//If we have a replacement node:
		//Replace the node we want to remove with this node
		if (replacementNode != NULL)
		{
			//Rebalance the tree between the node we want to delete and the replacement node
			T2AVLnode<T,D,inverted>* fixNode = replacementNode->getParent();
			T2AVLnode<T,D,inverted>* nextFixNode = NULL;

			while ((fixNode!=NULL) && (fixNode!=this))
			{
				nextFixNode = fixNode->getParent();
				fixNode->fixHeights();
				fixNode = nextFixNode;
			}

			//Replace the node we want to delete
			replacementNode->setRight(this->getRight());
			if (this->getRight()!=NULL)
				this->getRight()->setParent(replacementNode);

			replacementNode->setLeft(this->getLeft());
			if (this->getLeft()!=NULL)
				this->getLeft()->setParent(replacementNode);

			replacementNode->setParent(this->getParent());

			if (this->getParent()!=NULL)
			{
				if (this->getParent()->getLeft()==this)
					this->getParent()->setLeft(replacementNode);
				else
					this->getParent()->setRight(replacementNode);
			}

			//Rebalance the replacement node
			replacementNode->fixHeights();

			newParent = replacementNode;
		}

		left=NULL;
		right=NULL;
		parent = newParent;
		return this;
	}

	/*
	This function returns the node with the minimal key
	*/
	T2AVLnode<T,D,inverted>* getFirst()
	{
		//if there is no left subtree, this node is the first node
		if (left==NULL)
			return this;

		//else we search for the minimal key in the left subtree
		T2AVLnode<T,D,inverted>* temp = left;
		while(temp->getLeft()!=NULL)
		{
			temp=temp->getLeft();
		}
		return temp;
	}

	/*
	This function returns the node with the maximal key
	*/
	T2AVLnode<T,D,inverted>* getLast()
	{
		//if there is no right subtree, this node is the last node
		if (right==NULL)
			return this;

		//else we search for the maximal key in the right subtree
		T2AVLnode<T,D,inverted>* temp = right;
		while(temp->getRight()!=NULL)
		{
			temp=temp->getRight();
		}
		return temp;
	}

	/*
	Function to return the "next" value in the tree
	e.g. if there are 3 nodes with the values 1,3,5
	if we call this for 1 we get 3
	if we call this for 3 we get 5
	if we call this for 5 we get NULL
	this will be inverted if <inverted> is true
	*/
	T2AVLnode<T,D,inverted>* getNext()
	{
		T2AVLnode<T,D,inverted>* temp;
		//check if this node has a right subtree
		//return the minimal key of this subtree
		if (right!=NULL)
		{
			return right->getFirst();
		}

		if (parent!=NULL)
		{
			//If this node is the left child
			//return the parent node
			if (this == parent->getLeft())
				return parent;

			//If this is the right node:
			//travel up through the tree while we come from the right subtree
			//return the parent node
			else
			{
				temp = this;
				while(temp->getParent()->getRight()==temp)
				{
					temp=temp->getParent();

					//if we reached the tree root from its right subtree, return NULL)
					if (temp->getParent()==NULL)
						return NULL; 
				}
				if (temp->getParent()==NULL)
					return temp; //we reached the root
				else
					return temp->getParent();
			}
		}
		return NULL;
	}

	/*
	Function to return the "previous" value in the tree
	e.g. if there are 3 nodes with the values 1,3,5
	if we call this for 1 we get NULL
	if we call this for 3 we get 1
	if we call this for 5 we get 3
	this will be inverted if <inverted> is true
	*/
	T2AVLnode<T,D,inverted>* getPrev()
	{
		T2AVLnode<T,D,inverted>* temp;

		//check if this node has a left subtree
		//return the maximal key of this subtree
		if (left!=NULL)
		{
			return left->getLast();
		}

		if (parent!=NULL)
		{
			//If this node is the left child
			//return the parent node
			if (this == parent->getRight())
				return parent;

			//If this is the left node:
			//travel up through the tree while we come from the left subtree
			//return the parent node
			else
			{
				temp = this;
				while(temp->getParent()->getLeft()==temp)
				{
					temp=temp->getParent();

					//if we reached the tree root from its right subtree, return NULL)
					if (temp->getParent()==NULL)
						return NULL; 
				}
				if (temp->getParent()==NULL)
					return temp; //we reached the root
				else
					return temp->getParent();
			}
		}
		return NULL;
	}
};
#endif
